package com.zjj.algorithm.learning.dmsxl.dynamicplan;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 139. 单词拆分 中档题
 * <p>
 * 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
 * <p>
 * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
 * 示例 2：
 * <p>
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
 * 注意，你可以重复使用字典中的单词。
 * 示例 3：
 * <p>
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * <p>
 * 1 <= s.length <= 300
 * 1 <= wordDict.length <= 1000
 * 1 <= wordDict[i].length <= 20
 * s 和 wordDict[i] 仅有小写英文字母组成
 * wordDict 中的所有字符串 互不相同
 *
 * @author zjj_admin
 * @date 2023/1/31 10:26
 */
public class DynamicPlan_26_WorkBreak {

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("leet");
        wordDict.add("code");
        wordDict.add("sand");
        wordDict.add("and");
        wordDict.add("cat");

        boolean res = wordBreak(s, wordDict);
        System.out.println("res = " + res);

    }


    /**
     * 可以将问题转化为背包问题，单词就是物品，字符串就是背包，字符串能否由单词组成，就是看物品能不能够将背包填满。
     * dp[i]：字符串长度为 i 的话，当dp[i] 为 true 时，表示长度为 i 的字符串可以拆分成一个或者多个单词。
     * <p>
     * 时间
     * 12 ms
     * 击败
     * 9.38%
     * 内存
     * 41.7 MB
     * 击败
     * 34.65%
     *
     * @param s
     * @param wordDict
     * @return
     */
    public static boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        HashSet<String> set = new HashSet<>(wordDict);
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i && !dp[i]; j++) {
                if (set.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }


}
